10261 - Ferry loading/10261.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <climits>
   4 #include <vector>
   5
   6 using namespace std;
   7
   8 int capacity, n;
   9 vector<int> w;
  10
  11 int dp(int p, int s, int i){
  12   if (p > capacity || s > capacity)
  13     return INT_MIN;
  14   if (i >= n)
  15     return 0;
  16
  17   return max(dp(p + w[i], s, i+1) + 1, dp(p, s + w[i], i+1) + 1);
  18
  19 }
  20
  21 int main(){
  22   int C;
  23   cin >> C;
  24   while (C--){
  25     cin >> capacity;
  26     capacity *= 100;
  27
  28     w.clear();
  29     int x;
  30     while(cin >> x && x){
  31       w.push_back(x);
  32     }
  33
  34     n = w.size();
  35
  36     cout << dp(0,0,0) << endl;
  37   }
  38   return 0;
  39 }